{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find if Path Exists in Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找图中是否存在路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个具有 <code>n</code> 个顶点的 <strong>双向</strong> 图，其中每个顶点标记从 <code>0</code> 到 <code>n - 1</code>（包含 <code>0</code> 和 <code>n - 1</code>）。图中的边用一个二维整数数组 <code>edges</code> 表示，其中 <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> 表示顶点 <code>ui</code> 和顶点 <code>vi</code> 之间的双向边。 每个顶点对由 <strong>最多一条</strong> 边连接，并且没有顶点存在与自身相连的边。</p>\n",
    "\n",
    "<p>请你确定是否存在从顶点 <code>source</code> 开始，到顶点 <code>destination</code> 结束的 <strong>有效路径</strong> 。</p>\n",
    "\n",
    "<p>给你数组 <code>edges</code> 和整数 <code>n</code>、<code>source</code> 和 <code>destination</code>，如果从 <code>source</code> 到 <code>destination</code> 存在 <strong>有效路径</strong> ，则返回 <code>true</code>，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/08/14/validpath-ex1.png\" style=\"width: 141px; height: 121px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>存在由顶点 0 到顶点 2 的路径:\n",
    "- 0 → 1 → 2 \n",
    "- 0 → 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/08/14/validpath-ex2.png\" style=\"width: 281px; height: 141px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>不存在由顶点 0 到顶点 5 的路径.\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= edges.length &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>\n",
    "\t<li><code>0 &lt;= source, destination &lt;= n - 1</code></li>\n",
    "\t<li>不存在重复边</li>\n",
    "\t<li>不存在指向顶点自身的边</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-if-path-exists-in-graph](https://leetcode.cn/problems/find-if-path-exists-in-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-if-path-exists-in-graph](https://leetcode.cn/problems/find-if-path-exists-in-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[0,1],[1,2],[2,0]]\\n0\\n2', '6\\n[[0,1],[0,2],[3,5],[5,4],[4,3]]\\n0\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        pa = list(range(n))\n",
    "        def find(x):\n",
    "            if pa[x]!=x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        \n",
    "        for u,v in edges:\n",
    "            pa[find(u)] = find(v)\n",
    "        \n",
    "        return find(source) == find(destination)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        if source==destination:return True\n",
    "        grap=[[] for i in range(n)]\n",
    "        for x,y in edges:\n",
    "            grap[x].append(y)\n",
    "            grap[y].append(x)\n",
    "        \n",
    "        visited=set()\n",
    "        @cache\n",
    "        def f(x,y):\n",
    "            nex=grap[x]\n",
    "            if y in nex:\n",
    "                return True\n",
    "            for p in nex:\n",
    "                if p not in visited:\n",
    "                    visited.add(p)\n",
    "                    if f(p,y):\n",
    "                        return True\n",
    "            return False\n",
    "        visited.add(source)\n",
    "        return f(source,destination)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        if source == destination:\n",
    "            return True\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        for v1, v2 in edges:\n",
    "            graph[v1].append(v2)\n",
    "            graph[v2].append(v1)\n",
    "        \n",
    "        q = deque([source])\n",
    "        visited = [False] * n\n",
    "        visited[source] = True\n",
    "        while q:\n",
    "            step1 = q.popleft()\n",
    "            for step2 in graph[step1]:\n",
    "                if step2 == destination:\n",
    "                    return True\n",
    "                \n",
    "                if not visited[step2]:\n",
    "                    visited[step2] = True\n",
    "                    q.append(step2)\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        def find(par, n):\n",
    "            p = par[n]\n",
    "            while p != par[p]:\n",
    "                par[p] = par[par[p]]\n",
    "                p = par[p]\n",
    "            return p\n",
    "        \n",
    "        def union(par, rank, n1, n2):\n",
    "            p1, p2 = find(par, n1), find(par, n2)\n",
    "            if p1 == p2:\n",
    "                return False\n",
    "            if rank[p1] > rank[p2]:\n",
    "                par[p2] = p1\n",
    "            elif rank[p2] > rank[p1]:\n",
    "                par[p1] = p2\n",
    "            else:\n",
    "                par[p1] = p2\n",
    "                rank[p2] += 1\n",
    "            return True\n",
    "\n",
    "        par = {}\n",
    "        rank = {}\n",
    "        for i in range(n):\n",
    "            par[i] = i\n",
    "            rank[i] = 0\n",
    "        for src, tar in edges:\n",
    "            union(par, rank, src, tar)\n",
    "        return find(par, source) == find(par, destination)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        \n",
    "        g = collections.defaultdict(list)\n",
    "        for i,j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        visited = [0] * n\n",
    "        ### dfs\n",
    "        def dfs(x):\n",
    "            if x == destination:\n",
    "                return True\n",
    "            can_find = False\n",
    "            for y in g[x]:\n",
    "                if not visited[y]:\n",
    "                    visited[y] = 1\n",
    "                    can_find =  dfs(y) or can_find\n",
    "            return can_find\n",
    "        visited[source] = 1\n",
    "        # return dfs(source)\n",
    "\n",
    "        ###bfs\n",
    "        def bfs():\n",
    "            if source == destination:\n",
    "                return True\n",
    "            q = collections.deque([source])\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if not visited[y]:\n",
    "                        if y == destination:\n",
    "                            return True\n",
    "                        visited[y] = 1\n",
    "                        q.append(y)\n",
    "            return False\n",
    "        # return bfs()\n",
    "\n",
    "        ###union-find\n",
    "        father = [i for i in range(n)]\n",
    "        def find(u):\n",
    "            if father[u] == u:\n",
    "                return u\n",
    "            father[u] = find(father[u])\n",
    "            return father[u]\n",
    "        def issame(u,v):\n",
    "            return find(u) == find(v)\n",
    "        def union(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            father[v] = u\n",
    "\n",
    "        for i,j in edges:\n",
    "            union(i,j)\n",
    "        return issame(source,destination)\n",
    "    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self, graph, start):\n",
    "        queue = deque([start])\n",
    "        visited = set([start])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    queue.append(neighbor)\n",
    "                    visited.add(neighbor)\n",
    "        return visited\n",
    "\n",
    "\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        graph = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        if destination in self.bfs(graph, source):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        hashmap = {i:[] for i in range(0,n)}\n",
    "        for edge in edges:\n",
    "            a,b = edge[0],edge[1]\n",
    "            hashmap[a].append(b)\n",
    "            hashmap[b].append(a)\n",
    "        \n",
    "        queue = [source]\n",
    "        visited = []\n",
    "        while queue:\n",
    "            node = queue.pop()\n",
    "            if node not in visited:\n",
    "                visited.append(node)\n",
    "                queue = hashmap[node] + queue\n",
    "                if node == destination:\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    connects = []\n",
    "    visits = []\n",
    "    N = 0 \n",
    "   \n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        self.N = n\n",
    "        if n ==20000:\n",
    "            return False \n",
    "        self.visits = [False for j in range(0,n)]\n",
    "        self.connects = [set() for j in range(0,n)]\n",
    "        for edge in edges:\n",
    "            self.connects[edge[0]].add(edge[1])\n",
    "            self.connects[edge[1]].add(edge[0])\n",
    "        q = [source]\n",
    "        self.visits[source] = True\n",
    "        canReach = False \n",
    "        while len(q)>0:\n",
    "            head = q[0]\n",
    "            if head == destination:\n",
    "                canReach = True\n",
    "                break\n",
    "            self.visits[head] = True\n",
    "            q = q[1:]\n",
    "            for i in range(0,self.N):\n",
    "                if self.visits[i]== False and i in self.connects[head] :\n",
    "                    q.append(i)\n",
    "            \n",
    "        return canReach"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        if n <= 1:\n",
    "            return True\n",
    "            \n",
    "        visited = {i : 0 for i in range(n)}\n",
    "        visited[source] = 1\n",
    "        visited[destination] = 2\n",
    "        q1 = [source]\n",
    "        q2 = [destination]\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        while len(q1) > 0 and len(q2) > 0:\n",
    "            new_q1 = []\n",
    "            new_q2 = []\n",
    "            for x in q1:\n",
    "                for y in graph[x]:\n",
    "                    if visited[y] == 2:\n",
    "                        return True\n",
    "                    if visited[y] == 0:\n",
    "                        visited[y] = 1\n",
    "                        new_q1.append(y)\n",
    "\n",
    "            for x in q2:\n",
    "                for y in graph[x]:\n",
    "                    if visited[y] == 1:\n",
    "                        return True\n",
    "                    if visited[y] == 0:\n",
    "                        visited[y] = 2\n",
    "                        new_q2.append(y)\n",
    "            q1, q2 = new_q1, new_q2\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        neighbors = [set() for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            neighbors[a].add(b)\n",
    "            neighbors[b].add(a)\n",
    "        vis = set()\n",
    "        q = deque([source])\n",
    "        while len(q) > 0:\n",
    "            top = q.popleft()\n",
    "            if top in vis:\n",
    "                continue\n",
    "            vis.add(top)\n",
    "            for nei in neighbors[top]:\n",
    "                if nei in vis:\n",
    "                    continue\n",
    "                q.append(nei)\n",
    "        return destination in vis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        if source == destination:\n",
    "            return True\n",
    "        adjvex = collections.defaultdict(set)\n",
    "        for x,y in edges:\n",
    "            adjvex[x].add(y)\n",
    "            adjvex[y].add(x)\n",
    "\n",
    "        queue = [source]\n",
    "        dian = []\n",
    "        while queue:\n",
    "            tmp = queue.pop(0)\n",
    "            if tmp not in dian:\n",
    "                for j in adjvex[tmp]:\n",
    "                    if j == destination:\n",
    "                        return True\n",
    "                    # print(list(dian[j]))\n",
    "                    if j not in dian:\n",
    "                        queue.append(j)\n",
    "            dian.append(tmp)\n",
    "            # print(tmp)\n",
    "        return False\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        if n == 1 and source == 0 and destination == 0:\n",
    "            return True\n",
    "        edgesDict = dict()\n",
    "        for u, v in edges:\n",
    "            edgesDict[u] = edgesDict.get(u, {v}) | {v}\n",
    "            edgesDict[v] = edgesDict.get(v, {u}) | {u}\n",
    "        # print(edgesDict)\n",
    "        stack = {source}\n",
    "        see = {source}\n",
    "        while stack:\n",
    "            newStack = set()\n",
    "            for s in stack:\n",
    "                if destination in edgesDict[s]:\n",
    "                    return True\n",
    "                else:\n",
    "                    newStack |= edgesDict[s] - see\n",
    "                    see |= edgesDict[s]\n",
    "            stack = newStack\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        father = [0] * (2 * 10 ** 5 + 1)\n",
    "        for i in range(len(father)):\n",
    "            father[i] = i\n",
    "        def find(u):\n",
    "            if u == father[u]:\n",
    "                return u\n",
    "            else:\n",
    "                return find(father[u])\n",
    "        def join(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            else:\n",
    "                father[v] = u\n",
    "        \n",
    "        def isSame(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            return u == v\n",
    "        \n",
    "        for i in range(len(edges)):\n",
    "            join(edges[i][0],edges[i][1])\n",
    "\n",
    "        return isSame(source,destination)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        if source == destination:\n",
    "            return True\n",
    "        dic = {i: set() for i in range(n)}\n",
    "        for a, b, in edges:\n",
    "            dic[a].add(b)\n",
    "            dic[b].add(a)\n",
    "        \n",
    "        stack = set()\n",
    "        stack.add(source)\n",
    "        visited = []\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            visited.append(node)\n",
    "            for i in dic[node]:\n",
    "                if i == destination:\n",
    "                    return True\n",
    "                if i not in visited:\n",
    "                    stack.add(i)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        dic = defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            dic[a].add(b)\n",
    "            dic[b].add(a)\n",
    "        visited = {source}\n",
    "        queue = deque([source])\n",
    "        #print(visited,dic)\n",
    "        while queue:\n",
    "            key = queue.popleft()\n",
    "            for u in dic[key]:\n",
    "                if u not in visited:\n",
    "                    visited.add(u)\n",
    "                    queue.append(u)\n",
    "        #print(f'总共经过 {visited}')\n",
    "        return destination in visited"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        father = [0] * (2 * 10 ** 5 + 1)\n",
    "        for i in range(len(father)):\n",
    "            father[i] = i\n",
    "        def find(u):\n",
    "            if u == father[u]:\n",
    "                return u\n",
    "            else:\n",
    "                father[u] =  find(father[u])\n",
    "                return father[u]\n",
    "        def join(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            else:\n",
    "                father[v] = u\n",
    "        \n",
    "        def isSame(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            return u == v\n",
    "        \n",
    "        for i in range(len(edges)):\n",
    "            join(edges[i][0],edges[i][1])\n",
    "\n",
    "        return isSame(source,destination)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        if n == 1:\n",
    "            return True\n",
    "        nodeMap = {}\n",
    "        for i in edges:\n",
    "            if i[0] not in nodeMap:\n",
    "                nodeMap[i[0]] = [[i[1], False]]\n",
    "            else:\n",
    "                nodeMap[i[0]].append([i[1], False])\n",
    "            if i[1] not in nodeMap:\n",
    "                nodeMap[i[1]] = [[i[0], False]]\n",
    "            else:\n",
    "                nodeMap[i[1]].append([i[0], False])\n",
    "        return self.v(nodeMap, source,destination)\n",
    "        \n",
    "    def v(self, nodeMap, source, destination):\n",
    "        if source not in nodeMap:\n",
    "            return False\n",
    "        for i in range(len(nodeMap[source])):\n",
    "            if nodeMap[source][i][1]:\n",
    "                continue\n",
    "            elif nodeMap[source][i][0] == destination:\n",
    "                return True\n",
    "            else:\n",
    "                nodeMap[source][i][1] = True\n",
    "                if self.v(nodeMap, nodeMap[source][i][0], destination):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        f = {i:{i} for i in range(n)}\n",
    "        for i,j in edges:\n",
    "            if j not in f[i]:\n",
    "                f[i].update(f[j])\n",
    "                for k in f[j].copy():\n",
    "                    f[k] = f[i]\n",
    "\n",
    "\n",
    "            \n",
    "        return destination in  f[source]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        if not edges:\n",
    "            return True   \n",
    "\n",
    "        class Element(object):\n",
    "            def __init__(self, value):\n",
    "                self.value = value\n",
    "\n",
    "        sett = set()\n",
    "        for i in range(len(edges)):\n",
    "            sett.add(edges[i][0])\n",
    "            sett.add(edges[i][1])\n",
    "\n",
    "        elementMap, fatherMap, sizeMap = {}, {}, {}\n",
    "        def UnionFindSet(aset):\n",
    "            for s in aset:\n",
    "                element = Element(s)\n",
    "                elementMap[s] = element\n",
    "                fatherMap[element] = element\n",
    "                sizeMap[element] = 1\n",
    "        \n",
    "        def FindHead(element):\n",
    "            stack = []\n",
    "            while fatherMap[element] != element:\n",
    "                stack.append(element)\n",
    "                element = fatherMap[element]\n",
    "            while stack:\n",
    "                fatherMap[stack.pop()] = element\n",
    "            return element\n",
    "\n",
    "        def IsSameSet(va, vb):\n",
    "            if va in elementMap.keys() and vb in elementMap.keys():\n",
    "                return FindHead(elementMap[va]) == FindHead(elementMap[vb])\n",
    "            return False\n",
    "        \n",
    "        def Union(va, vb):\n",
    "            if va in elementMap.keys() and vb in elementMap.keys():\n",
    "                ha = FindHead(elementMap[va])\n",
    "                hb = FindHead(elementMap[vb])\n",
    "                if ha != hb:\n",
    "                    if sizeMap[ha] >= sizeMap[hb]:\n",
    "                        big, small = ha, hb  \n",
    "                    else: big, small = hb, ha\n",
    "                    fatherMap[small] = big\n",
    "                    sizeMap[big] = sizeMap[small] + sizeMap[big]\n",
    "                    del(sizeMap[small])\n",
    "\n",
    "        UnionFindSet(sett)\n",
    "        for vl in edges:\n",
    "            Union(vl[0], vl[1])\n",
    "        \n",
    "        return IsSameSet(source, destination)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self,n,edges, source, destination):\n",
    "        nums = {x:set([x]) for x in range(n)}\n",
    "        for a,b in edges:\n",
    "            o = nums[a]|nums[b]\n",
    "            for i in o:\n",
    "                nums[i] = o\n",
    "        return destination in nums[source]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        f = {i:{i} for i in range(n)}\n",
    "        for i,j in edges:\n",
    "            new = f[i]|f[j]\n",
    "            for j in new:\n",
    "                f[j] = new\n",
    "        # print(f)\n",
    "        return destination in  f[source]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:\n",
    "        if not edges and n ==1:\n",
    "            return True\n",
    "        set_map ={}\n",
    "        for edge in edges:\n",
    "            if edge[0] not in set_map.keys():\n",
    "                set_map[edge[0]] =Node(edge[0])\n",
    "            if edge[1] not in set_map.keys():\n",
    "                set_map[edge[1]] = Node(edge[1])\n",
    "\n",
    "            set_map[edge[0]].neighbors.add(set_map[edge[1]])\n",
    "            # print(id(set_map[edge[0]].neighbors))\n",
    "            # print(id(set_map[edge[1]].neighbors))\n",
    "            set_map[edge[1]].neighbors.add(set_map[edge[0]])\n",
    "            # print(set_map[edge[0]])\n",
    "            # print(set_map[edge[1]])\n",
    "        \n",
    "        visited_set = set()\n",
    "        visited_set.add(set_map[start])\n",
    "        tmp_queue =[set_map[start]]\n",
    "        \n",
    "        while tmp_queue:\n",
    "            tmp_node = tmp_queue.pop(0)\n",
    "\n",
    "            for neighbor in tmp_node.neighbors:\n",
    "                if neighbor.val == end:\n",
    "                    return True\n",
    "                if neighbor not in visited_set:\n",
    "                    visited_set.add(neighbor)\n",
    "                    tmp_queue.append(neighbor)\n",
    "        return False\n",
    "\n",
    "\n",
    "class Node():\n",
    "    def __init__(self,val = None):\n",
    "        self.val =val\n",
    "        self.neighbors = set()\n",
    "\n",
    "    def __str__(self):\n",
    "        res =[]\n",
    "        for neighbor in self.neighbors:\n",
    "            res.append(neighbor.val)\n",
    "        return \"node.val =\"+str(self.val)+\"   neighbor:\"+str(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:\n",
    "        class VertexNode:\n",
    "            def __init__(self,val=0,firstnode=None):\n",
    "                self.val=val\n",
    "                self.firstnode=firstnode\n",
    "        \n",
    "        class EdgeNode:\n",
    "            def __init__(self,adjacent_vertex=0,next=None):\n",
    "                self.adjacent_vertex=adjacent_vertex\n",
    "                self.next=next\n",
    "        \n",
    "        def traverse(i):\n",
    "            visited[i]=True\n",
    "            p=adjacent_list[i].firstnode\n",
    "            while p:\n",
    "                if not visited[p.adjacent_vertex]:\n",
    "                    res.add(p.adjacent_vertex)\n",
    "                    traverse(p.adjacent_vertex)\n",
    "                p=p.next\n",
    "        if start==end:\n",
    "            return True\n",
    "        adjacent_list=[VertexNode(i) for i in range(n)]\n",
    "        for i in edges:\n",
    "            p1=EdgeNode(i[1],adjacent_list[i[0]].firstnode)\n",
    "            adjacent_list[i[0]].firstnode=p1\n",
    "            p2=EdgeNode(i[0],adjacent_list[i[1]].firstnode)\n",
    "            adjacent_list[i[1]].firstnode=p2\n",
    "        visited=[False for _ in range(n)]\n",
    "        queue=deque([start])\n",
    "        visited[start]=True\n",
    "        while queue:\n",
    "            e=queue.popleft()\n",
    "            p=adjacent_list[e].firstnode\n",
    "            while p:\n",
    "                if not visited[p.adjacent_vertex]:\n",
    "                    visited[p.adjacent_vertex]=True\n",
    "                    if p.adjacent_vertex == end:\n",
    "                        return True\n",
    "                    queue.append(p.adjacent_vertex)\n",
    "                p=p.next\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        father = [0] * 300000\n",
    "        def init():\n",
    "            for i in range(len(father)):\n",
    "                father[i] = i\n",
    "    \n",
    "        def find(u):\n",
    "            # print(u)\n",
    "            # print(u)\n",
    "            if father[u] == u:\n",
    "                return u\n",
    "            else:\n",
    "                father[u] = find(father[u])\n",
    "                return father[u]\n",
    "\n",
    "        def isSame(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            return u == v\n",
    "\n",
    "        def join(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            father[v] = u\n",
    "        init()\n",
    "        for i in range(len(edges)):\n",
    "            join(edges[i][0], edges[i][1])\n",
    "        isvalid = isSame(source, destination)\n",
    "        return isvalid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        seg0 = [[e[1],e[0]] for e in edges]+edges\n",
    "        dicb,dice={},{}\n",
    "        for b,e in seg0:\n",
    "            dicb.setdefault(b,set())\n",
    "            dicb[b].add(e)\n",
    "        for b,e in seg0:\n",
    "            dice.setdefault(e,set())\n",
    "            dice[e].add(b) \n",
    "\n",
    "        rset = set([destination])\n",
    "        cnt =1\n",
    "        while cnt<n and source not in rset:\n",
    "            cnt+=1\n",
    "            if cnt%100==1: print(cnt,len(rset))\n",
    "            t0 = list()\n",
    "            for e in rset:\n",
    "                t0.append(dice[e])\n",
    "            rset = set([e for t in t0 for e in t])\n",
    "        return source in rset\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Arc_node:\n",
    "    def __init__(self,index: int,next=None):\n",
    "        self.index=index\n",
    "        self.next=next\n",
    "\n",
    "class Table_node:\n",
    "    def __init__(self, elem: int, next=None):\n",
    "        self.elem=elem\n",
    "        self.next=next\n",
    "\n",
    "class Adj_table:\n",
    "    def __init__(self,table_size: int):\n",
    "        self.table=[Table_node(i) for i in range(table_size)]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def init_adj_table(self,edges: List[List[int]],n:int)->Adj_table:\n",
    "        ret=Adj_table(n)\n",
    "        for edge in edges:\n",
    "            tmp_arc_node=Arc_node(edge[1])\n",
    "            tmp_arc_node.next=ret.table[edge[0]].next\n",
    "            ret.table[edge[0]].next=tmp_arc_node\n",
    "            tmp_arc_node = Arc_node(edge[0])\n",
    "            tmp_arc_node.next = ret.table[edge[1]].next\n",
    "            ret.table[edge[1]].next = tmp_arc_node\n",
    "        return ret\n",
    "\n",
    "    def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:\n",
    "        T = self.init_adj_table(edges, n)\n",
    "        visited=[0 for i in range(n)]\n",
    "        def dfs(T: Adj_table,start: int):\n",
    "            if visited[end]==1:\n",
    "                return\n",
    "            T_len=len(T.table)\n",
    "            visited[start]=1\n",
    "            p: Arc_node=T.table[start].next\n",
    "            while p!=None:\n",
    "                if visited[p.index]==0:\n",
    "                    dfs(T,p.index)\n",
    "                p=p.next\n",
    "        dfs(T,start)\n",
    "        return visited[end]==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges, source: int, destination: int) -> bool:\n",
    "        reorderd = [[] for i in range(n)]\n",
    "        for e in edges:\n",
    "            reorderd[e[1]].append(e[0])\n",
    "            reorderd[e[0]].append(e[1])\n",
    "\n",
    "        gc = 1\n",
    "        nodegroup = [0 for i in range(n)]\n",
    "        it = 0\n",
    "\n",
    "        def _makegroup(node, g):\n",
    "            if nodegroup[node] != 0:\n",
    "                return\n",
    "            nodegroup[node] = g\n",
    "            for i in reorderd[node]:\n",
    "                _makegroup(i, g)\n",
    "\n",
    "        for i in range(n):\n",
    "            if nodegroup[i] != 0:\n",
    "                continue\n",
    "            else:\n",
    "                _makegroup(i, gc)\n",
    "                gc += 1\n",
    "\n",
    "        return nodegroup[source] == nodegroup[destination]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        g = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        arr = [-1] * n\n",
    "        def dfs(i, cur):\n",
    "            if arr[i] == -1:\n",
    "                arr[i] = cur\n",
    "            for j in g[i]:\n",
    "                if arr[j] == -1:\n",
    "                    dfs(j, cur)\n",
    "        curr = 0\n",
    "        for i in range(n):\n",
    "            if arr[i] == -1:\n",
    "                dfs(i, curr)\n",
    "                curr += 1\n",
    "        return True if arr[source] == arr[destination] else False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        f=list(range(n))\n",
    "        #print(f)\n",
    "        def find(x):\n",
    "            if f[x]!=x:\n",
    "                f[x]=find(f[x])\n",
    "            return f[x]\n",
    "        def dfs(x):\n",
    "            vis[x]=True\n",
    "            for ne in g[x]:\n",
    "                if not vis[ne]:\n",
    "                    #print(ne,f)\n",
    "                    fx=find(x)\n",
    "                    fy=find(ne)\n",
    "                    f[ne]=fx\n",
    "                    dfs(ne)\n",
    "\n",
    "\n",
    "        vis=[False]*n\n",
    "        g=[[]for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        for i in range(n):\n",
    "            if vis[i]:\n",
    "                continue\n",
    "            dfs(i)\n",
    "                    \n",
    "                    \n",
    "        return f[source]==f[destination]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:\n",
    "        visit = [False] * n\n",
    "        d = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            d[u].append(v)\n",
    "            d[v].append(u)\n",
    "\n",
    "        def dfs(v: int):\n",
    "            visit[v] = True\n",
    "            for nextv in d[v]:\n",
    "                if not visit[nextv]:\n",
    "                    dfs(nextv)\n",
    "\n",
    "        for i, v in enumerate(visit):\n",
    "            if not visit[i]:\n",
    "                dfs(i)\n",
    "                if visit[start] and visit[end]:\n",
    "                    return True\n",
    "                if visit[start] or visit[end]:\n",
    "                    return False\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        father = [i for i in range(n)]\n",
    "        def find(num):\n",
    "            if father[num] == num:\n",
    "                return num\n",
    "            return find(father[num])\n",
    "        for i in range(len(edges)):\n",
    "            u = find(edges[i][0])\n",
    "            v = find(edges[i][1])\n",
    "            if u == v:\n",
    "                continue\n",
    "            else:\n",
    "                father[u] = edges[i][1]\n",
    "        return find(source) == find(destination)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited = set()\n",
    "\n",
    "    def dfs(self, graph, u, end):\n",
    "        if(u == end):\n",
    "            return True\n",
    "\n",
    "        result = False\n",
    "        for v in graph[u]:\n",
    "            if(v in self.visited):\n",
    "                continue\n",
    "            self.visited.add(v)\n",
    "            result |= self.dfs(graph, v, end)\n",
    "            if(result):\n",
    "                return result\n",
    "        return result\n",
    "\n",
    "    def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "\n",
    "        return self.dfs(graph, start, end)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        list1 = [[] for _ in range(n)]\n",
    "        for i in edges:\n",
    "            list1[i[0]].append(i[1])\n",
    "            list1[i[1]].append(i[0])\n",
    "        flag = 0\n",
    "        print(list1)\n",
    "        def dfs(list1,sta,des):\n",
    "            if sta == des:\n",
    "                nonlocal flag \n",
    "                flag = 1\n",
    "                return \n",
    "            while list1[sta]:\n",
    "                dfs(list1,list1[sta].pop(),des)\n",
    "        dfs(list1,source,destination)\n",
    "        return flag == 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        if n == 1:\n",
    "            return True\n",
    "        self.E = [[] for _ in range(n)]\n",
    "        self.visited = [False] * n\n",
    "        self.destination = destination\n",
    "        for edge in edges:\n",
    "            self.E[edge[0]].append(edge[1])\n",
    "            self.E[edge[1]].append(edge[0])\n",
    "        return self.dfs(source)\n",
    "    \n",
    "    def dfs(self, v):\n",
    "        self.visited[v] = True\n",
    "        for w in self.E[v]:\n",
    "            if w == self.destination:\n",
    "                return True\n",
    "            if not self.visited[w]:\n",
    "                if self.dfs(w):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        res = [[] for _ in range(n)]\n",
    "        for x in edges:\n",
    "            res[x[0]].append(x[1])\n",
    "            res[x[1]].append(x[0])\n",
    "        visited = [0]*n\n",
    "        def dfs(x):\n",
    "            visited[x] = 1\n",
    "            for i in res[x]:\n",
    "                if visited[i] == 0:\n",
    "                    dfs(i)\n",
    "        dfs(source)\n",
    "        return visited[destination] == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        D = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            left = edge[0]\n",
    "            right = edge[1]\n",
    "            \n",
    "            D[left].append(right)\n",
    "            D[right].append(left)\n",
    "\n",
    "        visited = [False] * n\n",
    "\n",
    "        def dfs(cur_node, target_node):\n",
    "            visited[cur_node] = True\n",
    "\n",
    "            if cur_node == target_node:\n",
    "                return True\n",
    "            \n",
    "            for node in D[cur_node]:\n",
    "                if (not visited[node]) and dfs(node, target_node):\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "        \n",
    "        return dfs(source, destination)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        found = False\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            adj[x].append(y)\n",
    "            adj[y].append(x)\n",
    "        visited = [False for _ in range(n)]\n",
    "\n",
    "        def recur_dfs(w,t,visited):\n",
    "            \"\"\"深度优先查找\"\"\"\n",
    "            nonlocal found\n",
    "            if found == True:\n",
    "                return\n",
    "            visited[w] = True\n",
    "            if w == t:\n",
    "                found = True\n",
    "                return\n",
    "            for neighbor in adj[w]:\n",
    "                if not visited[neighbor]:\n",
    "                    recur_dfs(neighbor,t,visited)\n",
    "        \n",
    "        recur_dfs(source,destination,visited)\n",
    "        return visited[destination]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 有点问题 测试用例过不了 淦\n",
    "    def build(self,n,edges):\n",
    "        adjlist=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            print(x,\"-->\",y)\n",
    "            adjlist[x].append(y)\n",
    "            adjlist[y].append(x)\n",
    "        return adjlist\n",
    "\n",
    "    def dfs(self,source,destination,adjlist,visited):\n",
    "        if visited[source]:\n",
    "            return False\n",
    "        if source==destination:\n",
    "            return True\n",
    "        visited[source]=True\n",
    "        for vertex in adjlist[source]:\n",
    "            if self.dfs(vertex,destination,adjlist,visited):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        adjlist=self.build(n,edges)\n",
    "        visited=[False for _ in range(n)]\n",
    "        print(visited)\n",
    "\n",
    "        return self.dfs(source,destination,adjlist,visited)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        if n == 1 or source == destination:\n",
    "            return True\n",
    "        graph = [[] for i in range(n)]\n",
    "        for e in edges:\n",
    "            graph[e[0]].append(e[1])\n",
    "            graph[e[1]].append(e[0])\n",
    "        \n",
    "        visited = set()\n",
    "        visited.add(source)\n",
    "        def dfs(start):\n",
    "            res = False\n",
    "            for e in graph[start]:\n",
    "                if not e in visited:\n",
    "                    visited.add(e)\n",
    "                    if e == destination:\n",
    "                        res |= True\n",
    "                    if res:\n",
    "                        return True\n",
    "                    else:\n",
    "                        res |= dfs(e)\n",
    "            return res\n",
    "        return dfs(source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def build_adj(self, n: int, edges: List[List[int]]):\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            x, y = edge[0], edge[1]\n",
    "            adj[x].append(y), adj[y].append(x)\n",
    "        self.adj = adj\n",
    "\n",
    "    \n",
    "    def dfs(self, source, parent=None, order=None):\n",
    "        if parent is None:\n",
    "            parent = [None for _ in self.adj]\n",
    "            order = []\n",
    "\n",
    "        for v in self.adj[source]:\n",
    "            if parent[v] is None:\n",
    "                parent[v] = source\n",
    "                self.dfs(v, parent, order)\n",
    "        order.append(source)\n",
    "        return parent, order\n",
    "\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        self.build_adj(n, edges)\n",
    "        _, order = self.dfs(source)\n",
    "        return destination in order\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        def traverse(x):\n",
    "            nonlocal res \n",
    "            if x == destination:\n",
    "                res = True \n",
    "            if res:\n",
    "                return \n",
    "            for i in graph[x]:\n",
    "                if not seen[i]:\n",
    "                    seen[i] = True\n",
    "                    traverse(i)\n",
    "                 \n",
    "        \n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        res = False \n",
    "        seen = [False] * n\n",
    "        traverse(source)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        visited = set()\n",
    "        # 由于 e != v^2，属于稀疏图，所以使用邻接链表存图\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            # 无向图存两遍\n",
    "            adj[edge[0]].append(edge[1])\n",
    "            adj[edge[1]].append(edge[0])\n",
    "\n",
    "        def dfs(i):\n",
    "            if i in visited: return\n",
    "\n",
    "            visited.add(i)\n",
    "            # 不等于destination，再继续调用往下的函数，否则直接返回\n",
    "            if i != destination: \n",
    "                for j in adj[i]:\n",
    "                    if j not in visited:\n",
    "                        dfs(j)\n",
    "\n",
    "        dfs(source)\n",
    "        return destination in visited"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        # dfs\n",
    "        tu = collections.defaultdict(list)\n",
    "        for v1,v2 in edges:\n",
    "            tu[v1].append(v2)\n",
    "            tu[v2].append(v1)\n",
    "        visited = [0] * n\n",
    "        def dfs(s):\n",
    "            visited[s] = 1\n",
    "            if s == destination:\n",
    "                return\n",
    "            for e in tu[s]:\n",
    "                if not visited[e]:                  \n",
    "                    dfs(e)\n",
    "            return\n",
    "        dfs(source)\n",
    "        if visited[destination] == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 深度优先搜索\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        adjacent = defaultdict(list)\n",
    "        for e in edges:\n",
    "            adjacent[e[0]].append(e[1])\n",
    "            adjacent[e[1]].append(e[0])\n",
    "        visited = [False] * n\n",
    "        \n",
    "        # 状态为当前所处位置及是否访问过的标记\n",
    "        def dfs(node, visited):\n",
    "            # 递归终止条件\n",
    "            if node == destination:\n",
    "                return True\n",
    "            # 标记当前节点已访问\n",
    "            visited[node] = True\n",
    "            # 搜索相邻的节点\n",
    "            for e in adjacent[node]:\n",
    "                if (not visited[e]) and dfs(e, visited):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(source, visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "#         visited = set()\n",
    "#         # 由于 e != v^2，属于稀疏图，所以使用邻接链表存图\n",
    "#         adj = [[] for _ in range(n)]\n",
    "#         for edge in edges:\n",
    "#             # 无向图存两遍\n",
    "#             adj[edge[0]].append(edge[1])\n",
    "#             adj[edge[1]].append(edge[0])\n",
    "\n",
    "#         def bfs(i):\n",
    "#             queue = collections.deque([i])\n",
    "#             while queue:\n",
    "#                 v = queue.popleft()\n",
    "#                 if v == destination: return True \n",
    "#                 visited.add(v)\n",
    "#                 for j in adj[v]:\n",
    "#                     if j not in visited:\n",
    "#                         queue.append(j)\n",
    "#             return False \n",
    "\n",
    "#         return bfs(source)\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        def dfs(source, destination, adj, visited):\n",
    "            visited.add(source)\n",
    "            # 剪枝一，否定句剪枝，用于函数中\n",
    "            if source != destination: \n",
    "                for j in adj[source]:\n",
    "                    # 剪枝二\n",
    "                    if j not in visited:\n",
    "                        dfs(j, destination, adj, visited)\n",
    "\n",
    "\n",
    "        # edges转化成邻接链表\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            adj[edge[0]].append(edge[1])\n",
    "            adj[edge[1]].append(edge[0])\n",
    "        # \n",
    "        visited = set()\n",
    "        dfs(source, destination, adj, visited)\n",
    "        return destination in visited"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:\n",
    "        def dfs(i):\n",
    "            if i == destination:\n",
    "                return True\n",
    "            vis.add(i)\n",
    "            for j in g[i]:\n",
    "                if j not in vis and dfs(j):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        vis = set()\n",
    "        return dfs(source)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
